package list

// Problem Definition: https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e?tpId=117&tqId=37832&rp=1
func maxSquare(matrix [][]int) int {
	h := len(matrix)
	if h == 0 {
		return h
	}

	w := len(matrix[0])
	dp := make([][]int, h+1)
	for i := range dp {
		dp[i] = make([]int, w+1)
	}

	var ret int
	for i := 1; i <= h; i++ {
		for j := 1; j <= w; j++ {
			if matrix[i-1][j-1] == 1 {
				dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
				ret = max(ret, dp[i][j])
			}
		}
	}

	return ret * ret
}
